package com.yulongtian.offers.day202211.day20221102;

/**
 * https://leetcode.cn/problems/jian-sheng-zi-lcof/?favorite=xb9nqhhg
 *
 * 解决
 * @author yulongTian
 * @create 2022-11-02 15:09
 */
public class Test01 {
    public static void main(String[] args) {
        System.out.println(cuttingRope(58));
    }

    public static int cuttingRope(int n) {
        if (n == 2) {
            return 1;
        }

        if (n == 3) {
            return 2;
        }

        if (n == 4) {
            return 4;
        }

        if (n == 5) {
            return 6;
        }

        if (n == 6) {
            return 9;
        }

        int[] arr = new int[n + 1];

        arr[2] = 1;
        arr[3] = 2;
        arr[4] = 4;
        arr[5] = 6;
        arr[6] = 9;


        for (int i = 7; i < n + 1; i++) {
            for (int j = 1; j < i - 2; j++) {
                if (arr[i - j] * j >= arr[i - j - 1] * (j + 1)) {
                    arr[i] = arr[i - j] * j;
                    break;
                }
            }
        }

        return arr[n];
    }

}
